数据结构如何在Java中实现n:m关系？

Question

我需要在Java中实现一个n:m关系。 用例是一个目录

• 一个产品可以分为多个类别
• 一个类别可以容纳多个产品

我当前的解决方案是使用一个具有两个hashmaps的映射类

• 第一个hashmap的键是产品id，值是类别id的列表
• 第二个hashmap的键是category id，值是产品id的列表

这是完全冗余的，我需要一个设置类，该类始终注意在两个哈希映射中存储/删除数据

但这是我在O（1）中发现的实现以下性能的唯一方法：

• 哪些产品属于某一类别
• 产品属于哪些类别

我想在各个方面避免全阵列扫描或类似的事情

但必须有另一个更优雅的解决方案，我不需要对数据进行两次索引

请给我点灯。我只有纯Java，没有数据库或SQLite或其他可用的东西。如果可能的话，我也不想实现btree结构

Answer 1

如果您能够使用不可变的数据结构，Guava的ImmutableMultimap提供了一个inverse()方法，它允许您按值获取密钥集合

Answer 2

你的解决方案非常好。请记住，将对象放入HashMap并不会复制该对象，它只存储对该对象的引用，因此时间和内存成本非常小

Answer 3

如果您通过成员集合将类别与产品关联，而vica通过成员集合将类别与产品关联，则您可以完成相同的任务：

public class Product {
     private Set<Category> categories = new HashSet<Category>();
     //implement hashCode and equals, potentially by id for extra performance
}

public class Category {
     private Set<Product> contents = new HashSet<Product>();
     //implement hashCode and equals, potentially by id for extra performance
}

唯一困难的部分是填充这样的结构，其中可能需要一些中间映射

但使用辅助哈希映射/树进行索引的方法并不坏。毕竟，大多数放在数据库上的索引都是辅助数据结构：它们与行表共存；这些行不一定按索引本身的结构组织

使用这样的外部结构可以使优化和数据彼此分离；这不是坏事。尤其是如果明天你想为某个供应商提供的产品添加O（1）查找，例如

编辑：顺便说一句，您想要的似乎是一个Multimap的实现，它也经过了优化，可以在O（1）中进行反向查找。我不认为Guava可以做到这一点，但是你可以实现Multimap接口，这样至少你不需要单独维护HashMaps实际上，它更像是一个双贴图，也是一个多重贴图，这与它们的定义相矛盾。我同意MStodd的观点，您可能希望使用自己的抽象层来封装这两个映射

Answer 4

我同意你的第一个解决方案。在两个HashMap周围有一个抽象层。如果您担心并发性，请为CRUD实现适当的锁定